#!/usr/bin/env python
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年11月17日
版    本：v1.0.0
描    述：
Copyright (C) 2019 All rights reserved.
'''
class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """

        pairs.sort(key=lambda x: x[1])

        size = len(pairs)
        dp = [1 for _ in range(size)]
        for i in range(size-2, -1, -1):
            for j in range(i+1, size):
                if pairs[i][1] < pairs[j][0]:
                    dp[i] = max(dp[i+1], 1 + dp[j])
                    break

        return dp[0]


class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """

        pairs.sort(key=lambda x: x[1])

        size = len(pairs)
        res = 1
        end = pairs[0][1]
        for i in range(1, size):
            if pairs[i][0] > end:
                res += 1
                end = pairs[i][1]
        
        return res
